﻿namespace Leetcode.N0410;
public class Solution
{
    public int SplitArray(int[] nums, int m)
    {
        var sums = new int[nums.Length + 1];
        for (int i = 1; i < sums.Length; i++)
        {
            sums[i] = nums[i - 1] + sums[i - 1];
        }

        var ans = new int[sums.Length][];
        ans[0] = new int[m + 1];
        for (int i = 1; i < sums.Length; i++)
        {
            ans[i] = new int[m + 1];
            for (int blockIndex = 1; blockIndex <= Math.Min(i, m); blockIndex++)
            {
                var minValue = this.GetMinValue(ans, sums, blockIndex, i);
                ans[i][blockIndex] = minValue;
            }
        }
        return ans[ans.Length - 1][m];
    }

    private int GetMinValue(int[][] ans, int[] sums, int blockIndex, int endIndex)
    {
        if (blockIndex == 1)
        {
            return sums[endIndex];
        }

        int minValue = int.MaxValue;

        for (int i = endIndex; i >= blockIndex; i--)
        {
            var val = Math.Max(sums[endIndex] - sums[i - 1], ans[i - 1][blockIndex - 1]);
            if (val > minValue)
            {
                break;
            }
            minValue = val;
        }
        return minValue;
    }

}
